home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 08 / bowlst.aug next >
Text File  |  1987-08-12  |  15KB  |  405 lines
  1.      1: /*
  2.      2:  *
  3.      3:  *                              KROSS.C
  4.      4:  *
  5.      5:  *                COPYRIGHT (C) 1987 by Charles F. Bowman
  6.      6:  *
  7.      7:  *                        ALL RIGHTS RESERVED.
  8.      8:  *
  9.      9:  */
  10.     10: #include        "stdio.h"
  11.     11: 
  12.     12: #define NIL     '\000'
  13.     13: 
  14.     14: #define ALL     1
  15.     15: #define PUZ     2
  16.     16: #define DOWN    1
  17.     17: #define ACROSS  2
  18.     18: 
  19.     19: #define MINWORD 3
  20.     20: #define MAXPUZ  25
  21.     21: #define MAXWORD 50
  22.     22: #define WORDLEN 15
  23.     23: 
  24.     24: #define EMPTY   0
  25.     25: #define FREE    1
  26.     26: #define USED    2
  27.     27: #define SOLVED  3
  28.     28: 
  29.     29: #define BLANK   ' '
  30.     30: #define PADCHAR '-'
  31.     31: #define WORDS   "@words"
  32.     32: #define PUZZLE  "@puzzle"
  33.     33: 
  34.     34: #define FLAG(x, y)      list[ x - MINWORD ].w[ y ].flg
  35.     35: #define WORD(x, y)      list[ x - MINWORD ].w[ y ].word
  36.     36: 
  37.     37: FILE    *fp;
  38.     38: int     length, width;
  39.     39: char    puzzle[ MAXPUZ ][ MAXPUZ ];
  40.     40: 
  41.     41: struct  words   {
  42.     42:         char    word[ WORDLEN ];
  43.     43:         int     flg;
  44.     44: };
  45.     45: 
  46.     46: struct  {
  47.     47:         struct  words   w[ MAXWORD ];
  48.     48: } list[ WORDLEN - MINWORD ];
  49.     49: 
  50.     50: main( ac, av )
  51.     51: int     ac;
  52.     52: char    *av[];
  53.     53: {
  54.     54: 
  55.     55:         if( ac != 2 ){
  56.     56:                 fprintf( stderr, "usage: kross puzzlefile\n" );
  57.     57:                 exit( 1 );
  58.     58:         }
  59.     59:         if( (fp = fopen( av[1], "r" )) == NULL ){
  60.     60:                 fprintf( stderr, "Cannot open '%s' to read!\n", av[1] );
  61.     61:                 exit( 2 );
  62.     62:         }
  63.     63: 
  64.     64:         readpuz( fp );
  65.     65:         if( solve(0, -1) ){
  66.     66:                 pprint( PUZ );
  67.     67:         } else {
  68.     68:                 printf( "No Solution!!\n" );
  69.     69:         }
  70.     70:         exit( 0 );
  71.     71: }
  72.     72: 
  73.     73: /*
  74.     74:  *      =============================================================
  75.     75:  *              READPUZ(): read puzzle into memory from file
  76.     76:  *      =============================================================
  77.     77:  */
  78.     78: readpuz()
  79.     79: {
  80.     80:         int     i;
  81.     81:         char    buf[ 85 ];
  82.     82: 
  83.     83: 
  84.     84:         length = 0;
  85.     85:         /*
  86.     86:          *      Puzzle Section
  87.     87:          */
  88.     88:         if( fgets( buf, sizeof buf, fp ) == NULL ){
  89.     89:                 fprintf( stderr, "%s: Premature EOF!\n", PUZZLE );
  90.     90:                 exit( 4 );
  91.     91:         }
  92.     92:         if( strncmp( buf, PUZZLE, strlen( PUZZLE ) ) ){
  93.     93:                 fprintf( stderr, "%s: BAD FORMAT!\n", PUZZLE );
  94.     94:                 exit( 5 );
  95.     95:         }
  96.     96: 
  97.     97:         if(fgets(buf,sizeof buf,fp)==NULL
  98.     98:            || !strncmp(buf,WORDS,strlen(WORDS))){
  99.     99:                 fprintf( stderr, "%s: Premature EOF!\n", PUZZLE );
  100.    100:                 exit( 4 );
  101.    101:         }
  102.    102:         width = strlen( buf ) - 1;
  103.    103: 
  104.    104:         do {
  105.    105:                 if( (strlen( buf ) - 1) != width ){
  106.    106:                         fprintf(stderr,"Line %d: bad width!\n", width);
  107.    107:                         exit( 5 );
  108.    108:                 }
  109.    109:                 for( i = 0; i < width; i++ ){
  110.    110:                         if( buf[ i ] == BLANK ){
  111.    111:                                 puzzle[ length ][ i ] = NIL;
  112.    112:                         } else if( buf[i] == PADCHAR ){
  113.    113:                                 puzzle[ length ][ i ] = buf[ i ];
  114.    114:                         } else {
  115.    115:                                 fprintf(stderr,"BAD CHAR '%d' L# %d\n",
  116.    116:                                         buf[i], length );
  117.    117:                                 exit( 88 );
  118.    118:                         }
  119.    119:                 }
  120.    120:                 puzzle[ length ][ width ] = NIL;
  121.    121:                 length += 1;
  122.    122:         } while(fgets(buf,sizeof buf,fp)!=NULL &&
  123.    123:                 strncmp( WORDS, buf, strlen(WORDS) ) != 0 );
  124.    124: 
  125.    125:         /*
  126.    126:          *      Words Section
  127.    127:          */
  128.    128:         while( fgets( buf, sizeof buf, fp ) != NULL ){
  129.    129:                 for( i = 0; i < MAXWORD; i++ ){
  130.    130:                         if( FLAG( strlen(buf) - 1, i ) == EMPTY ){
  131.    131:                                 strncpy( WORD( strlen(buf) - 1, i ),
  132.    132:                                         buf, strlen(buf)-1 );
  133.    133:                                 FLAG( strlen(buf) - 1, i ) = FREE;
  134.    134:                         }
  135.    135:                 }
  136.    136:                 if( i >= MAXWORD ){
  137.    137:                         fprintf( stderr, "Out of space %d %s\n",
  138.    138:                                  strlen(buf)-1, buf );
  139.    139:                         exit( 6 );
  140.    140:                 }
  141.    141:         }
  142.    142:         return;
  143.    143: }
  144.    144: 
  145.    145: /*
  146.    146:  *      =============================================================
  147.    147:  *              PPRINT(): display solved pzzle
  148.    148:  *      =============================================================
  149.    149:  */
  150.    150: pprint( t )
  151.    151: int     t;
  152.    152: {
  153.    153:         int     i, j;
  154.    154: 
  155.    155:         switch( t ){
  156.    156:         case ALL:
  157.    157:                 /*
  158.    158:                  *      Debug only!
  159.    159:                  */
  160.    160:                 for( i = MINWORD; i < WORDLEN; i++ ){
  161.    161:                         j = 0;
  162.    162:                         while( WORD(i, j)[0] != NIL ){
  163.    163:                                 printf( "%s\n", WORD(i, j) );
  164.    164:                                 j++;
  165.    165:                         }
  166.    166:                 }
  167.    167: 
  168.    168:         case PUZ:
  169.    169:                 for( i = 0; i < length; i++ ){
  170.    170:                         for( j = 0; j < width; j++ ){
  171.    171:                                 if( puzzle[ i ][ j ] ){
  172.    172:                                         putchar( puzzle[ i ][ j ] );
  173.    173:                                 } else {
  174.    174:                                         putchar( BLANK );
  175.    175:                                 }
  176.    176:                         }
  177.    177:                         putchar( '\n' );
  178.    178:                 }
  179.    179:         }
  180.    180: 
  181.    181:         return;
  182.    182: }
  183.    183: 
  184.    184: /*
  185.    185:  *      =============================================================
  186.    186:  *              SOLVE(): function that searches for a solution
  187.    187:  *      =============================================================
  188.    188:  */
  189.    189: static  int     s = 0;
  190.    190: static  int     prev = -1;
  191.    191: 
  192.    192: solve( length, width )
  193.    193: int     length, width;
  194.    194: {
  195.    195:         int     l, w, i, len, tmp, type;
  196.    196:         char    old[ WORDLEN - MINWORD + 1 ];
  197.    197: 
  198.    198:         w = width;
  199.    199:         l = length;
  200.    200:         len = next( &l, &w, &type );
  201.    201:         if( len == 0 )
  202.    202:                 return( SOLVED );
  203.    203: 
  204.    204:         for( i = 0; i < MAXWORD && WORD(len, i)[0] != NIL; i++ ){
  205.    205:                 if( FLAG(len, i) == FREE
  206.    206:                     && itfits(l, w, WORD(len, i), type) ){
  207.    207:                         FLAG(len, i) = USED;
  208.    208:                         enter( old, l, w, WORD(len, i), type );
  209.    209:                         prev = type;
  210.    210:                         tmp = solve( l, w );
  211.    211:                         if( tmp == SOLVED )
  212.    212:                                 return( SOLVED );
  213.    213:                         restore( old, l, w, type );
  214.    214:                         FLAG(len, i) = FREE;
  215.    215:                 }
  216.    216:         }
  217.    217: 
  218.    218:         return( 0 );
  219.    219: }
  220.    220: 
  221.    221: /*
  222.    222:  *      =============================================================
  223.    223:  *              NEXT(): locate next slot to fill
  224.    224:  *      =============================================================
  225.    225:  */
  226.    226: next( len, wht, t )
  227.    227: int     *len, *wht, *t;
  228.    228: {
  229.    229:         /*
  230.    230:          *      Return the next slot in the puzzle to attempt
  231.    231:          *      to be solved. DOWN has precedence.
  232.    232:          *
  233.    233:          *      The new values for len & wht will be updated.
  234.    234:          *      The returned value for the 'w' coordinate for
  235.    235:          *      an across 'hit' will have to be the value + 1.
  236.    236:          */
  237.    237:         int     l, w, tmp;
  238.    238: 
  239.    239:         l = *len;
  240.    240:         w = *wht;
  241.    241: 
  242.    242:         /*
  243.    243:          *      Check current position for across: down would
  244.    244:          *      have been done already.
  245.    245:          */
  246.    246:          if( w != -1 &&  ( (w - 1) < 0 || puzzle[l][w-1] == NIL )
  247.    247:          && puzzle[l][w] && (w + 1) < width && puzzle[l][w+1] ){
  248.    248:                 /*
  249.    249:                  *      Across!
  250.    250:                  */
  251.    251:                 *t = ACROSS;
  252.    252: 
  253.    253:                 /*
  254.    254:                  *      Neccessary Evil!
  255.    255:                  */
  256.    256:                 *wht = w + 1;
  257.    257: 
  258.    258:                 tmp = 0;
  259.    259:                 while( puzzle[l][w] != NIL && w < width ){
  260.    260:                         w += 1;
  261.    261:                         tmp += 1;
  262.    262:                 }
  263.    263:                 return( tmp );
  264.    264: 
  265.    265:         } else if( prev == DOWN || w == -1 ){
  266.    266:                 w += 1;
  267.    267:         }
  268.    268: 
  269.    269:         /*
  270.    270:          *      Check for next possible position
  271.    271:          */
  272.    272:         for(; l < length; l += 1 ){
  273.    273:                 for(; w < width; w += 1 ){
  274.    274:                         if( ( (l - 1) < 0 || puzzle[l-1][w] == NIL )
  275.    275:                         && puzzle[l][w] != NIL && (l + 1) < length
  276.    276:                         && puzzle[l+1][w] != NIL ){
  277.    277:                                 /*
  278.    278:                                  *      Down!
  279.    279:                                  */
  280.    280:                                 *t = DOWN;
  281.    281:                                 prev = DOWN;
  282.    282:                                 *wht = w;
  283.    283:                                 *len = l;
  284.    284:                                 tmp = 0;
  285.    285:                                 while(puzzle[l][w]!=NIL && l<length){
  286.    286:                                         l += 1;
  287.    287:                                         tmp += 1;
  288.    288:                                 }
  289.    289:                                 return( tmp );
  290.    290:                         }
  291.    291:                         if( ((w - 1) < 0 || puzzle[l][w-1] == NIL)
  292.    292:                             && puzzle[l][w] && (w+1) < width
  293.    293:                             && puzzle[l][w+1] ){
  294.    294:                                 /*
  295.    295:                                  *      Across!
  296.    296:                                  */
  297.    297:                                 *t = ACROSS;
  298.    298:                                 prev = ACROSS;
  299.    299:                                 *len = l;
  300.    300:                                 *wht = w + 1;
  301.    301: 
  302.    302:                                 tmp = 0;
  303.    303:                                 if( w == -1 ) w = 0;
  304.    304:                                 while(puzzle[l][w] != NIL && w<width){
  305.    305:                                         w += 1;
  306.    306:                                         tmp += 1;
  307.    307:                                 }
  308.    308:                                 return( tmp );
  309.    309:                         }
  310.    310:                 }
  311.    311:                 w = 0;
  312.    312:         }
  313.    313: 
  314.    314:         /*
  315.    315:          *      Puzzle Completed!
  316.    316:          */
  317.    317:         return( 0 );
  318.    318: }
  319.    319: 
  320.    320: /*
  321.    321:  *      =============================================================
  322.    322:  *              ITFITS(): determine is a word fits into a slot
  323.    323:  *      =============================================================
  324.    324:  */
  325.    325: itfits( l, w, word, t )
  326.    326: char    *word;
  327.    327: int     t;
  328.    328: {
  329.    329:         char    *cp;
  330.    330: 
  331.    331:         if( t == ACROSS && w != -1)
  332.    332:                 w -= 1;
  333.    333: 
  334.    334:         cp = word;
  335.    335:         while( *cp ){
  336.    336:                 if( *cp != puzzle[l][w] && puzzle[l][w] != PADCHAR )
  337.    337:                         return( 0 );
  338.    338:                 if( t == ACROSS )
  339.    339:                         w += 1;
  340.    340:                 else
  341.    341:                         l += 1;
  342.    342:                 cp++;
  343.    343:         }
  344.    344:         return( 1 );
  345.    345: }
  346.    346: 
  347.    347: /*
  348.    348:  *      =============================================================
  349.    349:  *              ENTER(): enter word into puzzle
  350.    350:  *      =============================================================
  351.    351:  */
  352.    352: enter( old, l, w, word, t )
  353.    353: char    *old;
  354.    354: int     l, w;
  355.    355: char    *word;
  356.    356: int     t;
  357.    357: {
  358.    358:         char    *cp;
  359.    359: 
  360.    360:         if( t == ACROSS )
  361.    361:                 w -= 1;
  362.    362: 
  363.    363:         cp = word;
  364.    364:         while( *cp ){
  365.    365:                 *old++ = puzzle[l][w];
  366.    366:                 puzzle[l][w] = *cp;
  367.    367:                 if( t == ACROSS )
  368.    368:                         w += 1;
  369.    369:                 else
  370.    370:                         l += 1;
  371.    371:                 cp++;
  372.    372:         }
  373.    373:         *old = NIL;
  374.    374: 
  375.    375:         return;
  376.    376: }
  377.    377: 
  378.    378: /*
  379.    379:  *      =============================================================
  380.    380:  *              RESTORE(): restore puzzle to prev state
  381.    381:  *      =============================================================
  382.    382:  */
  383.    383: restore( old, l, w, t )
  384.    384: char    *old;
  385.    385: int     l, w, t;
  386.    386: {
  387.    387:         char    *cp;
  388.    388: 
  389.    389:         if( t == ACROSS )
  390.    390:                 w -= 1;
  391.    391: 
  392.    392:         cp = old;
  393.    393:         while( *cp ){
  394.    394:                 puzzle[l][w] = *cp;
  395.    395:                 if( t == ACROSS )
  396.    396:                         w += 1;
  397.    397:                 else
  398.    398:                         l += 1;
  399.    399:                 cp++;
  400.    400:         }
  401.    401: 
  402.    402:         return;
  403.    403: }
  404.  
  405.